package com.dataStructure.图;

import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

//图中对外开发的只有图定点的值，以及边上的权值。
public abstract class 图<V,E> {
    public 图() {
    }

    public 图(WeightManager<E> weightManager) {
        this.weightManager = weightManager;
    }

    //增
    //添加一个顶点
    public abstract void addVertex(V v);
    //添加一条边
    public abstract void addEdge(V from, V to);
    //添加一条带权值的边
    public abstract void addEdge(V from, V to,E weight);

    //删
    //移除一个顶点
    public abstract void removeVertext(V v);
    //移除一条边
    public abstract void removeEdge(V from,V to);

    //查
    //返回边的数量
    public abstract int edgesSize();
    //返回顶点的数量
    public abstract int verticseSize();

    //遍历
    //广度优先遍历，参照二叉树的层序遍历 Breadth First Search
    public abstract void bfs_non_recursive(V begin,VertexVisitor<V> visitor);
    //深度优先遍历(Depth First Search)，参照二叉树的前序遍历（递归）
    public abstract void dfs_recursion(V begin,VertexVisitor<V> visitor);
    //深度优先遍历(Depth First Search)，参照二叉树的前序遍历（非递归）
    public abstract void dfs_non_recursive(V begin,VertexVisitor<V> visitor);

    //遍历接口
    interface VertexVisitor<V>{
        boolean visit(V v) ;
    }

    //定义一个图权值的管理器，专门用于图权值的比较，加权，定义权值为0的情况 等操作
    protected WeightManager<E> weightManager;
    public interface WeightManager<E>{
        int compare(E w1,E w2);
        E add(E w1, E w2);
        E zero();
    }

    //拓扑排序（有向无环图）
    public abstract List<V> topologicalSort();

    //最小生成树
    public abstract Set<EdgeInfo<V,E>> mst();
    //此类用于最小生成树的返回值（不直接返回图的内部类Edge的原因是不暴露原有内部的类型）
    public static class EdgeInfo<V,E>{
        private V from;
        private V to;
        private E weight;

        protected EdgeInfo(V from, V to, E weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public V getFrom() {
            return from;
        }

        public void setFrom(V from) {
            this.from = from;
        }

        public V getTo() {
            return to;
        }

        public void setTo(V to) {
            this.to = to;
        }

        public E getWeight() {
            return weight;
        }

        public void setWeight(E weight) {
            this.weight = weight;
        }
    }

    //最短路径
    public abstract Map<V,PathInfo<V,E>> shortestPath(V begin);
    //多元最短路径
    public abstract Map<V,Map<V,PathInfo<V,E>>> shortestPath();
    //最短路径的信息，包含要走的路径的总权值，路径中包含的边
    public static class PathInfo<V,E>{
        //总权值
        protected E weight;
        //最短路径中包含的边
        protected List<EdgeInfo<V,E>> edgeInfos = new LinkedList<>();

        public PathInfo() {
        }

        public PathInfo(E weight) {
            this.weight = weight;
        }

        public E getWeight() {
            return weight;
        }

        public void setWeight(E weight) {
            this.weight = weight;
        }

        public List<EdgeInfo<V, E>> getEdgeInfos() {
            return edgeInfos;
        }

        public void setEdgeInfos(List<EdgeInfo<V, E>> edgeInfos) {
            this.edgeInfos = edgeInfos;
        }

        @Override
        public String toString() {
            return "PathInfo{" +
                    "weight=" + weight +
                    ", edgeInfos=" + edgeInfos +
                    '}';
        }
    }


}
